package cn.demoncat.util.lang;

import cn.demoncat.util.lang.entity.data.LinkedStack;
import cn.demoncat.util.lang.entity.data.SingleLinkedList;
import org.apache.commons.lang3.StringUtils;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 计算器
 * 
 * @author 延晓磊
 *
 * @since 2020年6月29日
 */
public class CalculateUtil {

	/**
	 * 运算符优先级
	 */
	public static final Map<String, Integer> OPERATOR_PRIORITY = new HashMap<String, Integer>(){
		private static final long serialVersionUID = 1L;
	{
		put("(", 0);
		put(")", 0);
		put("+", 1);
		put("-", 1);
		put("*", 2);
		put("/", 2);
	}};
	
	/**
	 * 后缀表达式计算 - 逆波兰算法（推荐）
	 * 
	 * @param expression	中缀表达式：1 + 2 - 3 * (4 + 5) / -6.7
	 * 
	 * @return 计算结果
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月29日
	 */
	public static Double calcPostfix(String expression) {
		return calcPostfix(toPostfix(splitInfix(expression)));
	}
	
	/**
	 * 前缀表达式计算 - 波兰算法
	 * 
	 * @param expression	中缀表达式：1 + 2 - 3 * (4 + 5) / -6.7
	 * 
	 * @return 计算结果
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月29日
	 */
	public static Double calcPrefix(String expression) {
		return calcPrefix(toPrefix(splitInfix(expression)));
	}
	
	/**
	 * 后缀表达式计算
	 * 
	 * @param postfixExpression	后缀表达式列表：[1, 2, +, 3, 4, 5, +, *, -6.7, /, -]
	 * 
	 * @return 计算结果
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月29日
	 */
	public static Double calcPostfix(List<String> postfixExpression) {
		// 运算栈
		LinkedStack<String> stack = new LinkedStack<>();
		// 遍历表达式：从左到右
		double n1;
		double n2;
		for (String item : postfixExpression) {
			if (item.matches(RegexpUtil.NumberRex.ALL)) {
				// 运算数：直接入栈
				stack.push(item);
			}else {
				// 运算符：弹出栈顶的2个数值并运算，结果再入栈
				n2 = Double.parseDouble(stack.pop());
				n1 = Double.parseDouble(stack.pop());
				switch (item) {
				case "+":
					stack.push(String.valueOf(n1 + n2));
					break;
				case "-":
					stack.push(String.valueOf(n1 - n2));
					break;
				case "*":
					stack.push(String.valueOf(n1 * n2));
					break;
				case "/":
					stack.push(String.valueOf(n1 / n2));
					break;
				default:
					// 不支持的运算符
					throw new RuntimeException("不支持运算符：" + item);
				}
			}
		}
		// 返回最终结果
		return Double.valueOf(stack.pop());
	}
	
	/**
	 * 前缀表达式计算
	 * 
	 * @param prefixExpression	前缀表达式列表：[-, +, 1, 2, /, *, 3, +, 4, 5, -6.7]
	 * 
	 * @return 计算结果
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月29日
	 */
	public static Double calcPrefix(List<String> prefixExpression) {
		// 运算栈
		LinkedStack<String> stack = new LinkedStack<>();
		// 遍历表达式：从右到左
		double n1;
		double n2;
		String item;
		for (int i = prefixExpression.size()-1; i >= 0; i--) {
			item = prefixExpression.get(i);
			if (item.matches(RegexpUtil.NumberRex.ALL)) {
				// 运算数：直接入栈
				stack.push(item);
			}else {
				// 运算符：弹出栈顶的2个数值并运算，结果再入栈
				n1 = Double.parseDouble(stack.pop());
				n2 = Double.parseDouble(stack.pop());
				switch (item) {
				case "+":
					stack.push(String.valueOf(n1 + n2));
					break;
				case "-":
					stack.push(String.valueOf(n1 - n2));
					break;
				case "*":
					stack.push(String.valueOf(n1 * n2));
					break;
				case "/":
					stack.push(String.valueOf(n1 / n2));
					break;
				default:
					// 不支持的运算符
					throw new RuntimeException("不支持运算符：" + item);
				}
			}
		}
		// 返回最终结果
		return Double.valueOf(stack.pop());
	}
	
	/**
	 * 将中缀表达式，转换为后缀表达式（逆波兰算法）
	 * 
	 * @param infixExpression	中缀表达式列表：[1, +, 2, -, 3, *, (, 4, +, 5, ), /, -6.7]
	 * 
	 * @return 后缀表达式列表：[1, 2, +, 3, 4, 5, +, *, -6.7, /, -]
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月29日
	 */
	public static List<String> toPostfix(List<String> infixExpression) {
		// 运算符栈
		LinkedStack<String> stack = new LinkedStack<>();
		// 表达式列表
		List<String> list = new ArrayList<>();
		// 从左到右扫描中缀表达式
		String curr;
		for (int i = 0; i < infixExpression.size(); i++) {
			curr = infixExpression.get(i);
			if (curr.matches(RegexpUtil.NumberRex.ALL)) {
				// 运算数：直接放入列表
				list.add(curr);
			}else if (curr.equals("(")) {
				// 左括号，直接入栈
				stack.push(curr);
			}else if (curr.equals(")")) {
				// 右括号：将栈中运算符依次弹出，放入列表，直至遇到左括号时停止（括号清除：右括号未入栈，左括号出栈）
				while (true) {
					curr = stack.pop();
					if (curr.equals("(")) {
						// 左括号：停止弹出
						break;
					}else {
						// 运算符：放入列表
						list.add(curr);
					}
				}
			}else {
				// 运算符：依次检测栈顶运算符和当前运算符的优先级
				while (true) {
					// 栈为空：直接入栈，停止检测
					if (stack.isEmpty()) {
						stack.push(curr);
						break;
					}
					// 栈非空：比较优先级
					if (OPERATOR_PRIORITY.get(curr).compareTo(OPERATOR_PRIORITY.get(stack.peek())) > 0) {
						// 当前运算符优先于栈顶运算符：当前运算符入栈，停止检测
						stack.push(curr);
						break;
					}else {
						// 当前运算符优先于栈顶运算符：弹出栈顶运算符，放入列表
						list.add(stack.pop());
					}
				}
			}
		}
		// 扫描完毕：将栈中运算符依次弹出，放入列表
		while (!stack.isEmpty()) {
			list.add(stack.pop());
		}
		// 返回列表
		return list;
	}
	
	/**
	 * 将中缀表达式，转换为前缀表达式（波兰算法）
	 * 
	 * @param infixExpression	中缀表达式列表：[1, +, 2, -, 3, *, (, 4, +, 5, ), /, -6.7]
	 * 
	 * @return 前缀表达式列表：[-, +, 1, 2, /, *, 3, +, 4, 5, -6.7]
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月29日
	 */
	public static List<String> toPrefix(List<String> infixExpression) {
		// 运算符栈
		LinkedStack<String> stack = new LinkedStack<>();
		// 表达式列表
		SingleLinkedList<String> list = new SingleLinkedList<>();
		// 从右到左扫描中缀表达式
		String curr;
		for (int i = infixExpression.size()-1; i >= 0; i--) {
			curr = infixExpression.get(i);
			if (curr.matches(RegexpUtil.NumberRex.ALL)) {
				// 运算数：直接放入列表
				list.add(curr);
			}else if (curr.equals(")")) {
				// 右括号，直接入栈
				stack.push(curr);
			}else if (curr.equals("(")) {
				// 左括号：将栈中运算符依次弹出，放入列表，直至遇到右括号时停止（括号清除：左括号未入栈，右括号出栈）
				while (true) {
					curr = stack.pop();
					if (curr.equals(")")) {
						// 右括号：停止弹出
						break;
					}else {
						// 运算符：放入列表
						list.add(curr);
					}
				}
			}else {
				// 运算符：依次检测栈顶运算符和当前运算符的优先级
				while (true) {
					// 栈为空：直接入栈，停止检测
					if (stack.isEmpty()) {
						stack.push(curr);
						break;
					}
					// 栈非空：比较优先级
					if (OPERATOR_PRIORITY.get(curr).compareTo(OPERATOR_PRIORITY.get(stack.peek())) < 0) {
						// 栈顶运算符优先于当前运算符：弹出栈顶运算符，放入列表
						list.add(stack.pop());
					}else {
						// 栈顶运算符不优先于当前运算符：当前运算符入栈，停止检测
						stack.push(curr);
						break;
					}
				}
			}
		}
		// 扫描完毕：将栈中运算符依次弹出，放入列表
		while (!stack.isEmpty()) {
			list.add(stack.pop());
		}
		// 翻转链表
		return list.reverse().toList();
	}
	
	/**
	 * 切割中缀表达式
	 * 
	 * @param expression	中缀表达式：1 + 2 - 3 * (4 + 5) / -6.7
	 * 
	 * @return 中缀表达式列表：[1, +, 2, -, 3, *, (, 4, +, 5, ), /, -6.7]
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年6月29日
	 */
	public static List<String> splitInfix(String expression){
		// 去除空白
		expression = StringUtils.deleteWhitespace(expression);
		// 切割字符
		char[] chars = expression.toCharArray();
		// 整理
		ArrayList<String> list = new ArrayList<>();
		StringBuilder num = new StringBuilder();
		for (char c : chars) {
			switch (c) {
			case '(':
			case ')':
			case '+':
			case '*':
			case '/':
				// 保存运算数：运算数 > 运算符，运算数 > )，运算符 > (，) > 运算符
				if (num.length() > 0) {
					list.add(num.toString());
					num = new StringBuilder();
				}
				// 保存运算符
				list.add(c + "");
				break;
			case '-':
				if (num.length() > 0) {
					// 保存运算数：运算数之后的-，表示减号
					list.add(num.toString());
					num = new StringBuilder();
					// 保存运算符
					list.add("-");
				}else {
					// 拼接运算数：非运算数之后的-，表示负号
					num = new StringBuilder("-");
				}
				break;
			default:
				// 拼接运算数
				num.append(c);
				break;
			}
		}
		list.add(num.toString());
		return list;
	}
	
 
	
}
